The present invention relates to network communication systems. It finds particular application in conjunction with controlling admission of Voice-Over IP (VoIP) calls to a packet-based network, and efficiently selecting paths for the admitted calls, so as to balance the packet loads within the network. However, it is to be appreciated that the present invention is also amenable to any type of service requiring connection management, irrespective of traffic burstiness or other factors, and to other like applications such as TCP requiring admission control, video or data transport where a need exists to improve the quality of service (QoS) of data transfer over a network including network scenarios with multiple applications having distinct QoS constraints.
The internet, intranets, and other internet protocol (IP) networks are handling ever increasing volumes of data. Beyond the worldwide web and e-mail capabilities of such networks, applications and protocols are being developed to further add to the volume of traffic. Among these are voice related applications such as telephony or Voice-Over IP, and video applications, such as video telephony, video conferencing, and the like. Unfortunately, even at current usage levels packet loss due to congestion is becoming problematic degrading the performance of data transfer.
Streams of packets typically enter the network from packet switching edge devices or gateways which serve as portals to the interconnected web of routers comprising the network. Typically these gateways are indiscriminant in their treatment of packet streams in that they merely port the packet streams onto the network without regard for congestion levels or likelihood of the packets reaching their final destination. Moreover, the networks typically are unaware of any coherence or association among packet streams, and merely forward individual packets from router to router on a first-come-first-served basis, without regard to their relative priorities. These two limitations severely constrain the ability to provide quality-of-service guarantees for real-time services such as voice in IP-based networks.
Some attempts have been made to address portions of this problem. For example, packet prioritization schemes such as differentiated services or Diffserv distinguish packet streams among several classes. Protocols are also evolving which route higher priority packets more reliably, for example, by allocating certain bandwidth on links between routers for each class. Another partial solution that has been articulated is that of establishing explicit routing paths through the network between frequently traveled points. Multi-protocol label switching (MPLS) is a protocol which enables a label to be assigned to a packet stream which specifies a predetermined path through the network. This allows better monitoring and control of congestion over the paths taken by voice streams, for example. However, the problem introduced by edge-devices not being aware of the congestion levels within the interior of the network still remains. One strategy being pursued to tackle this limitation is to dedicate a certain amount of bandwidth for each MPLS path, on each network link that it traverses. This creates a set of voice trunks among all pairs of nodes, much akin to the telephone trunk routes currently employed between circuit switches, and hence abandon the inherent flexibility afforded by the IP network. In particular, this strategy does not lead to a scalable solution. The number of trunks grows as the square of the number of edge nodes, and the consequent bandwidth fragmentation among hundreds or thousands of MPLS paths can exhaust the link capacities rather quickly. Furthermore, the servicing and provisioning of the multitude of voice trunks across the network are both cumbersome and slow to accommodate new nodes within the network.
The present invention contemplates a new and improved method and apparatus for call management over IP networks which overcomes the above-referenced problems and others associated with the existing approaches.
The above problems are alleviated and an advance is made over the prior art in accordance with the teachings of applicants"" invention wherein, a method of regulating admission of packet streams to a network includes at selected times sending path status messages along a set of paths in the network. A cost metric in each path status message is updated at the intermediate nodes as the message progresses along its defined path. Based on the final cost metric values collected upon receipt of the status messages at the respective path edges, subsequent packet stream arrivals are selectively blocked or admitted to the network.
In accordance with another aspect of the present invention, the method further provides choosing an optimal path between a source and a destination gateway.
In accordance with another aspect of the present invention, the paths through the network include a plurality of interconnected links, each potentially operating at different capacities or utilizations. The xe2x80x9cchoosing an optimal pathxe2x80x9d step optionally includes determining a most utilized bottleneck link for each of the alternative path choices through the network (for the source and destination gateways in question), and then selecting the path whose bottleneck link is the least utilized among the set of bottleneck links corresponding to the available path choices.
In accordance with another aspect of the invention, the paths through the network include a plurality of interconnected links, each path potentially having different numbers of links. The xe2x80x9cchoosing an optimal pathxe2x80x9d step optionally includes selecting a path through the network based on the combination criteria of having smaller bottleneck link utilization and having fewer links compared to other paths.
In accordance with another aspect of the present invention, the path includes a plurality of links interconnecting routers. The xe2x80x9cupdating a cost metricxe2x80x9d step includes measuring link usage at the routers.
In accordance with another aspect of the present invention, each path is comprised of links that are adapted to discriminate between different classes of packet streams. The xe2x80x9cupdating a cost metricxe2x80x9d step includes measuring usage by individual class.
In accordance with another embodiment of the present invention, a system for controlling admission of a packet stream along a path includes a plurality of routers adapted to update a cost metric in a path status message upon receipt of the message at each router. The system further includes a plurality of links interconnecting the routers where selected links and routers together comprise the path through the network.
In accordance with another aspect of the present invention, the plurality of routers are further adapted to generate, and send, the path status message along the determined path at selected times.
In accordance with another aspect of the present invention, the system alternately includes a gateway adapted to generate, and send, the path status message along the predetermined path at selected times.
In accordance with another aspect of the present invention, each of the plurality of routers is further adapted to select an optimum path through the network in response to receipt of a packet stream admission request.
In accordance with another aspect of the present invention, the plurality of routers are further adapted to discriminate between path status messages, and other (payload) packets.
In accordance with another aspect of the present invention, the plurality of links interconnecting the routers are adapted to discriminate between classes of packet streams, e.g., via Weighted Fair Queuing or WFQ.
In accordance with another embodiment of the present invention, a method includes sending a path status message along a defined path and, as the path message progresses through a plurality of routers in the path, updating a cost metric in the path status message at the routers that it transits through.
In accordance with another aspect of the present invention, the method further includes generating an indicator where the indicator shows an optimal path between a source and a destination, or where the indicator shows that no path presently meets admission control criteria.
In accordance with another aspect of the present invention, the xe2x80x9cgenerating an indicatorxe2x80x9d step showing that an optimal path exists between a given source destination node pair optionally includes determining a most utilized bottleneck link for each candidate path through the network between these two nodes. The method further includes optionally selecting as the optimal path, the path whose bottleneck link utilization is the smallest among the set of bottleneck links of the candidate paths, and placing an identifier for the selected optimal path into the path status message.
In accordance with another aspect of the present invention, the xe2x80x9cgenerating an indicatorxe2x80x9d step to show an optimal path optionally includes selecting a path through the network based on the combination criteria of having smaller bottleneck link utilization and having fewer links compared to other path alternatives.
In accordance with another aspect of the present invention, the method further includes discriminating between path status messages and other (payload) packets.
In accordance with another aspect of the present invention, xe2x80x9cthe updating a cost metricxe2x80x9d step includes measuring link usage at individual routers.
In accordance with another aspect of the present invention, each path is comprised of a set of links which are adapted to discriminate between classes of packet streams, and the xe2x80x9cupdating a cost metricxe2x80x9d step includes determining cost data by packet class.
One advantage of the present invention resides in accurately sensing individual link utilizations by periodically measuring traffic flow.
Another advantage of the present invention resides in the system being distributed across the network, thus not requiring any centralized database.
Still another advantage of the present invention resides in providing quality of service guarantees to packet streams entering the network.
Still another advantage of the present invention resides in the inherent flexibility and scalability of the call admission and load balancing systems.
Still further advantages and benefits of the present invention will become apparent to those of ordinary skill in the art upon reading and understanding the following detailed description of the preferred embodiments.